#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int DataType;

typedef struct QListNode
{
	struct QListNode* next;
	DataType data;

} QNode;

typedef struct Queue
{
	DataType size;
	QNode* phead;
	QNode* ptail;
} QList;

void QueueInit(QList* q);

void QueueDestroy(QList* q);

void QueuePush(QList* q, DataType x);

void QueuePop(QList* q);

DataType QueueFront(QList* q);

DataType QueueBack(QList* q);

bool QueueEmpty(QList* q);

DataType QueueSize(QList* q);

void QueueInit(QList* q)
{
	assert(q);
	q->phead = NULL;
	q->ptail = NULL;
	q->size = 0;
}

void QueuePush(QList* q, DataType x)
{
	assert(q);
	if (QueueEmpty(q))
	{
		QNode* newnode = (QNode*)malloc(sizeof(QNode));
		newnode->data = x;
		newnode->next = NULL;
		q->phead = newnode;
		q->ptail = newnode;
		q->size++;
	}
	else
	{
		QNode* newnode = (QNode*)malloc(sizeof(QNode));
		q->ptail->next = newnode;
		q->ptail = newnode;
		newnode->data = x;
		q->size++;
	}
}

void QueueDestroy(QList* q)
{
	assert(q);
	QNode* cur = q->phead;
	while (cur != q->ptail)
	{
		QNode* tmp = cur;
		cur = cur->next;
		free(tmp);
	}
	free(q->phead);
	free(q->ptail);
	q->phead = q->ptail = NULL;
}

void QueuePop(QList* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->phead == q->ptail)
	{
		free(q->phead);
		q->phead = q->ptail = NULL;
		q->size--;
	}
	else
	{
		QNode* cur = q->phead->next;
		free(q->phead);
		q->phead = cur;
		q->size--;
	}
}

DataType QueueFront(QList* q)
{
	return q->phead->data;
}

DataType QueueBack(QList* q)
{
	return q->ptail->data;
}

bool QueueEmpty(QList* q)
{
	return q->phead == NULL && q->ptail == NULL && q->size == 0;
}

DataType QueueSize(QList* q)
{
	return q->size;
}


typedef struct {
	QList q1;
	QList q2;
} MyStack;


MyStack* myStackCreate() {
	MyStack* st = (MyStack*)malloc(sizeof(MyStack));
	QueueInit(&st->q1);
	QueueInit(&st->q2);
	return st;
}

void myStackPush(MyStack* obj, int x) {
	if (!QueueEmpty(&obj->q1))
	{
		QueuePush(&obj->q1, x);
	}
	else
	{
		QueuePush(&obj->q2, x);
	}
}

int myStackPop(MyStack* obj) {
	if (!QueueEmpty(&obj->q1))
	{
		while (QueueSize(&obj->q1) > 1)
		{
			QueuePush(&obj->q2, QueueFront(&obj->q1));
			QueuePop(&obj->q1);
		}
		int top = QueueFront(&obj->q1);
		QueuePop(&obj->q1);
		return top;
	}
	else
	{
		while (QueueSize(&obj->q2) > 1)
		{
			QueuePush(&obj->q1, QueueFront(&obj->q2));
			QueuePop(&obj->q2);
		}
		int top = QueueFront(&obj->q2);
		QueuePop(&obj->q2);
		return top;
	}
}

int myStackTop(MyStack* obj) {
	if (!QueueEmpty(&obj->q1))
	{
		return QueueBack(&obj->q1);
	}
	else
	{
		return QueueBack(&obj->q2);
	}
}

bool myStackEmpty(MyStack* obj) {
	return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
	free(obj);
}

int main()
{
	MyStack* ms=myStackCreate();
	myStackPush(ms, 1);
	myStackPush(ms, 2);
	int k = myStackTop(ms);
	myStackPop(ms);
	return 0;
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);

 * int param_2 = myStackPop(obj);

 * int param_3 = myStackTop(obj);

 * bool param_4 = myStackEmpty(obj);

 * myStackFree(obj);
*/